// Copyright 2011 Jefferson Willian
// willmont7@gmail.com

/* Processa componentes fortemente conectados */
/*
v         -> Vertice atual
index     -> Ordem da DFS
low       -> Menor indice-ordem DFS do componente que o elemento esta conectado
mainStack -> Indices do processo da DFS
*/
void tarjan_solve(vector<int> (*graph)[MAX], int v, int* count, int index[], int low[], int id[], stack<int>* mainStack) {
  int t;
  vector<int>::iterator it;

  /* Coloca o indice na pilha */
  mainStack->push(v);
  /* Seta valores para index e low */
  index[v] = low[v] = (*count)++;

  /* Processa todos os vertices que v conecta */
  for (it = (*graph)[v].begin();it != (*graph)[v].end();++it) {
    t = *it;
    /* Verifica se o vertice nao foi visitado ainda */
    if (index[t] == -1) {
      tarjan_solve(graph, t, count, index, low, id, mainStack);
      /* Verifica se ele tem um melhor menor-indice-componente(low) */
      if (low[t] < low[v]) low[v] = low[t];
    } else { if (index[t] < low[v]) low[v] = index[t]; }
    /* Se ja foi visitado verifica se o seu index eh melhor */
  }

  /* Se idnex[v] == low[v] entao o elemento principal do componente jah foi processado */
  if (index[v] == low[v]) {
    /* Identifica todos os vertices ligados a ele como um mesmo componente */
    do {
      t = mainStack->top(); mainStack->pop();
      id[t+1] = id[0];
      index[t] = MAX;
    }while (t != v);
    /* Atualiza componente fortemente conectado */
    ++id[0];
  }

  return;
}

/* Algoritmo tarjan para descobrir componentes fortemente conectados      */
/* id[] -> Matriz com indices de componentes fortemente conectados (DFS2) */
void tarjan(vector<int> (*graph)[MAX], int n, int ind[]) {
  int index[MAX];
  int low[MAX];
  stack<int> mainStack;

  /* Seta valores iniciais para indexe low */
  for (int i = 0;i < n;i++) index[i] = low[i] = -1;

  int count = 0;   // Ordem de processo da DFS
  ind[0] = 0;      // Compenente atual
  /* Processa todos os elementos que nao foram processados */
  for (int i = 0;i < n;i++)
    if (low[i] == -1)
      tarjan_solve(graph, i, &count, index, low, ind, &mainStack);

  return;
}
